(в задаче коммивояжёра)

См. также в других словарях:

• Алгоритм ближайшего соседа в задаче коммивояжёра — Алгоритм ближайшего соседа  один из простейших эвристических методов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов. Формулируется следующим образом: Пункты обхода плана последовательно включаются в маршрут, причем,… …   Википедия

• Задача коммивояжёра — Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600. Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр …   Википедия

• Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра. Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из… …   Википедия

• Комбинаторный взрыв — термин, используемый для описания эффекта резкого («взрывного») роста временной сложности алгоритма при увеличении размера входных данных задачи[1]. Более точно это означает, что рассматриваемый алгоритм не является полиномиальным, то есть время… …   Википедия

• NP-полная задача — В теории алгоритмов NP полная задача  задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP полные задачи образуют в некотором смысле подмножество «самых сложных» задач в… …   Википедия

• Задача о ранце — Пример задачи о ранце: необходимо разместить ящики в рюкзак при условии на вместимость рюкзака 15 кг, так чтобы суммарная полезность предметов в рюкзаке была максимальной. Задача о ранце (рюкзаке) (англ.  …   Википедия

• Задача об упаковке в контейнеры — В теории сложности вычислений задача об упаковке в контейнеры NP трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число… …   Википедия

• Задача выполнимости булевых формул — (SAT или ВЫП) важная для теории вычислительной сложности алгоритмическая задача. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача заключается в следующем: можно ли… …   Википедия

• Задача о клике — относится к классу NP полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.[1] …   Википедия

• Задача о независимом наборе — Задача о независимом множестве относится к классу NP полных задач в области теории графов. По сути, она полностью эквивалентна задаче о клике. Независимый набор из 9 голубых вершин Множество вершин графа называется независимым, если никакие две… …   Википедия

• Задача о независимом множестве — относится к классу NP полных задач в области теории графов. Эквивалентна задаче о клике. Содержание 1 Определения 2 Максимальное независимое множество в дереве …   Википедия